package sort.leetcode;

/**
 * 剑指offer51-数组中的逆序对
 * https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
 * @author yuisama
 * @date 2021/12/23 14:39
 **/
public class Offer51 {
    // 归并思想求解数组逆序对问题
    public int reversePairs(int[] nums) {
        return reversePairsInternal(nums,0,nums.length - 1);
    }

    /**
     * 在nums[l..r]上求逆序对的个数
     * @param nums
     * @param l
     * @param r
     * @return
     */
    private int reversePairsInternal(int[] nums, int l, int r) {
        if (l >= r) {
            return 0;
        }
        int mid = l + (r - l) / 2;
        // 先求出已经排好序的左半区间逆序对个数
        int retLeft = reversePairsInternal(nums,l,mid);
        // 再求出已经排好序的右半区间逆序对个数
        int retRight = reversePairsInternal(nums,mid + 1,r);
        if (nums[mid] > nums[mid + 1]) {
            // 只有当左半边数组与右半边数组产生逆序时才merge
            // 最终在整个merge后的数组上求arr[l..r]的逆序对个数
            return retLeft + retRight + merge(nums,l,mid,r);
        }
        return retLeft + retRight;
    }

    /**
     * 将已经有序的nums[l..mid] 以及 nums[mid + 1..r]合并为整个有序数组，并求出合并后的逆序对个数
     * @param nums
     * @param l
     * @param mid
     * @param r
     * @return
     */
    private int merge(int[] nums, int l, int mid, int r) {
        int ret = 0;
        // 创建临时数组复制原数组值
        int[] aux = new int[r - l + 1];
        // 将原数组的值复制到temp中
        for (int i = l; i <= r; i++) {
            aux[i - l] = nums[i];
        }
        int i = l,j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                // 左半区间为空,继续放右半区间值
                nums[k] = aux[j - l];
                j ++;
            }else if (j > r) {
                // 右半区间为空，继续放左半区间值
                nums[k] = aux[i - l];
                i ++;
            }else if (aux[i - l] <= aux[j - l]) {
                // 将等于的情况放在左半区间
                nums[k] = aux[i - l];
                i ++;
            }else {
                // 此时右半区间值小于左半区间，则此时aux[j - l]与左半区间所以元素全部构成逆序对！
                nums[k] = aux[j - l];
                j ++;
                ret += (mid - i + 1);
            }
        }
        return ret;
    }
}